package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

public class _12_判断二叉树是否为平衡二叉树_01 {


    public static boolean isBalanceTree(TreeNode treeNode) {

        boolean[] res = new boolean[]{true};

        reversal(treeNode,res);
        return res[0];
    }

    /**
     * 如果在递归中要返回多个值，使用类作为返回值
     * @param treeNode
     * @return
     */
    public static int reversal(TreeNode treeNode, boolean[] res) {

        if (treeNode == null) {

            return 0;
        }

        int leftHeight = reversal(treeNode.left,res);

        if (!res[0]) {

            return 0;
        }

        int rightHeight = reversal(treeNode.right,res);

        if (!res[0]) {

            return 0;
        }

        if (Math.abs(leftHeight - rightHeight) > 1) {

            res[0] = false;
            return 0;
        }

        return Math.max(leftHeight,rightHeight) + 1;
    }

    public static void main(String[] args) {

        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(2);
        t1.left.left = new TreeNode(4);
        t1.left.left.left = new TreeNode(8);
        t1.left.left.right = new TreeNode(9);
        t1.left.right = new TreeNode(5);
        t1.left.right.left = new TreeNode(10);
        t1.right = new TreeNode(3);
//        t1.right.left = new TreeNode(6);
//        t1.right.right = new TreeNode(7);

        System.out.println(isBalanceTree(t1));

    }
}
